package java_thinking.unit_17._17_9_10;

import java_thinking.unit_17._17_2_6.Countries;

import java.util.*;

/**
 * @Desc:
 * @author: cww
 * @DateTime: 2019-04-19 22:43
 */

public class SimpleHashSet<K> extends AbstractSet<K> {
    private int SIZE = 997;
    @SuppressWarnings("unchecked")
    private LinkedList<K>[] buckets = new LinkedList[SIZE];

    @Override
    public boolean add(K k) {
        int index = Math.abs(k.hashCode()) % SIZE;
        if (buckets[index] == null) {
            buckets[index] = new LinkedList<>();
        }
        LinkedList<K> bucket = buckets[index];
        ListIterator<K> it = bucket.listIterator();
        while (it.hasNext()) {
            if (it.next().equals(k)) {
                return false;
            }
        }
        it.add(k);
        return true;
    }

    @Override
    public boolean contains(Object o) {
        int index = Math.abs(o.hashCode()) % SIZE;
        if (buckets[index] == null) return false;
        Iterator<K> it = buckets[index].iterator();
        while (it.hasNext()) {
            if (it.next().equals(o)) {
                return true;
            }
        }
        return false;
    }

    /**
     * 这里用两个index分别表示桶的指针和桶内的list指针，好办法！
     * @return
     */
    @Override
    public Iterator<K> iterator() {
        return new Iterator<K>() {
            private int count;
            private boolean canRemove;
            private int index1,index2;
            @Override
            public boolean hasNext() {
                return count < size();
            }

            @Override
            public K next() {
                if (hasNext()) {
                    canRemove = true;
                    ++count;
                    for(;;) {
                        while (buckets[index1] == null){
                            ++index1;
                        }
                        try {
                            return buckets[index1].get(index2++);
                        } catch (IndexOutOfBoundsException e) {
                            ++index1;
                            index2 = 0;
                        }
                    }
                }
                throw new NoSuchElementException();
            }

            @Override
            public void remove() {
                if (canRemove) {
                    canRemove = false;
                    buckets[index1].remove(--index2);
                    if (buckets[index1].isEmpty()) {
                        buckets[index1++] = null;
                    }
                    --count;
                }else {
                    throw new IllegalStateException();
                }
            }
        };
    }

    @Override
    public int size() {
        int sz = 0;
        for (LinkedList<K> bucket : buckets) {
            if (bucket != null) {
                sz += bucket.size();
            }
        }
        return sz;
    }

    public static void main(String[] args) {
        SimpleHashSet<String> m = new SimpleHashSet<String>();
        m.addAll(Countries.names(10));
        m.addAll(Countries.names(10));
        System.out.println("m = " + m);
        System.out.println("m.size() = " + m.size());
        Iterator<String> it = m.iterator();
        System.out.println("it.next()= "+ it.next());
        it.remove();
        System.out.println("it.next()= "+ it.next());
        System.out.println("m = " + m);
        m.remove("CAMEROON");
        System.out.println("m = " + m);
    }
}
